package day_2022_7_to_8.day48;

import java.util.LinkedList;
import java.util.List;

/**
 * 全排列1
 * @author haomin
 * @date 2022/07/16 10:11
 **/
// 2.复习各种算法的基本思想，算法框架，解题步骤等。例如：
//（1）回溯法的基本思想、算法的框架、用回溯法解决问题的步骤。
//答：基本思想：按照深度优先的策略，从根节点出发搜索解空间树。
// 算法搜索至解空间树的任一节点时，总是先判断该结点是否满足问题的约束条件。
// 如果满足进入该子树，继续按深度优先的策略进行搜索。否则，不去搜索以该结点为根的子树，
// 而是逐层向其祖先节点回溯。其实回溯法就是对隐式图的深度优先搜索算法加约束条件。
//算法框架：回溯法是一个既带有系统性又带有跳跃性的搜索算法。
//系统性指能够全面搜索；跳跃性则是可以有目的性地提前筛选掉不合格的解
//
// 解题步骤：①针对所有问题，定义问题的解空间；
// ②确定易于搜索的接空间结构；
//③以深度优先方式搜索解空间，并在搜索过程中用剪枝函数避免无效搜索。



public class Day2_1_Num46_Permute {
    public List<List<Integer>> result = new LinkedList<>();
    public List<Integer> ret = new LinkedList<>();

    public List<List<Integer>> permute(int[] nums) {
        dfs(nums,0,nums.length);
        return result;
    }

    public void dfs (int[] nums, int left, int right){
        if(ret.size() == right){        // 搜索到一个解，添加到result
            result.add(new LinkedList<>(ret));
        }
        for(int i = 0;i < right;i++){   // 还未回溯到头
            if(!ret.contains(nums[i])){
                ret.add(nums[i]);
                dfs(nums,left,right);   // 扩展下一个结点
                ret.remove(ret.size()-1);
            }
        }
    }
}